/*
 * Copyright (c) 2021
 * User:LENOVO
 * File:环形链表II.java
 * Date:2021/02/18 14:19:18
 */

package org.bytedance.链表和数;

import java.util.HashSet;
import java.util.Set;

public class 环形链表II {

    public static void main(String[] args) {
        环形链表II instance = new 环形链表II();
        ListNode head = new ListNode(3);
        head.next = new ListNode(5);
        head.next.next = new ListNode(2);
        head.next.next.next = new ListNode(4);
        boolean b = instance.circleList(head);
        System.out.println(b);
        head.next.next.next.next = head.next;
        b = instance.circleList(head);
        System.out.println(b);
        ListNode listNode = instance.circleList2(head);
        if (listNode == null) System.out.println("no circle in list");
        else System.out.println("circle start at the element of " + listNode.value);

        //快慢指针
        head.next.next.next.next = null;
        boolean b1 = instance.circleListQSPoint(head);
        System.out.println(b1);

        head.next.next.next.next = head.next.next;
        b1 = instance.circleListQSPoint(head);
        System.out.println(b1);
        ListNode listNode1 = instance.circleListQSPoint2(head);
        if (listNode1 == null) System.out.println("no circle in list");
        else System.out.println("circle start at the element of " + listNode1.value);

    }

    private static class ListNode {
        int value;
        ListNode next;

        public ListNode() {
        }

        public ListNode(int value) {
            this.value = value;
        }
    }

    /**
     * 使用hashset判断是否相交
     *
     * @param head
     * @return
     */
    public boolean circleList(ListNode head) {
        if (head == null || head.next == null) return false;
        Set<ListNode> visited = new HashSet<>();
        ListNode p = head;
        while (p != null) {
            if (!visited.add(p)) return true;
            p = p.next;
        }
        return false;
    }

    public ListNode circleList2(ListNode head) {
        if (head == null || head.next == null) return null;
        Set<ListNode> visited = new HashSet<>();
        ListNode p = head;
        while (p != null) {
            if (!visited.add(p)) return p;
            p = p.next;
        }
        return null;
    }

    /**
     * 使用快慢指针判断是否存在相交
     */
    public boolean circleListQSPoint(ListNode head) {
        if (head == null || head.next == null) return false;
        ListNode fast = null, slow = null;
        fast = slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) return true;
        }
        return false;
    }


    /**
     * 使用快慢指针判断是否存在相交
     */
    public ListNode circleListQSPoint2(ListNode head) {
        if (head == null || head.next == null) return null;
        ListNode fast = null, slow = null;
        fast = slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow){
                System.out.println("circle in list");
                break;
            }
        }
        if (fast == null || fast.next == null) return null;
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}
